{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Pile Box LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pileBox"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #堆箱子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>堆箱子。给你一堆n个箱子，箱子宽 wi、深 di、高 hi。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。</p>\n",
    "\n",
    "<p>输入使用数组<code>[wi, di, hi]</code>表示每个箱子。</p>\n",
    "\n",
    "<p><strong>示例1:</strong></p>\n",
    "\n",
    "<pre><strong> 输入</strong>：box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]\n",
    "<strong> 输出</strong>：6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例2:</strong></p>\n",
    "\n",
    "<pre><strong> 输入</strong>：box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]]\n",
    "<strong> 输出</strong>：10\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>箱子的数目不大于3000个。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [pile-box-lcci](https://leetcode.cn/problems/pile-box-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [pile-box-lcci](https://leetcode.cn/problems/pile-box-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box.sort(key=lambda x: -x[-1])\n",
    "        n = len(box)\n",
    "        res = 0\n",
    "        \n",
    "        # @cache\n",
    "        # def dfs(w, d, h, idx):\n",
    "        #     if idx == n:\n",
    "        #         return h\n",
    "        #     res = 0\n",
    "        #     for i in range(idx, n):\n",
    "        #         if box[i][0] < w and box[i][1] < d and box[i][2] < h:\n",
    "        #             res = max(res, dfs(box[i][0], box[i][1], box[i][2], i+1))\n",
    "        #     return res+h\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     res = max(res, dfs(box[i][0], box[i][1], box[i][2], i+1))\n",
    "        # return res\n",
    "\n",
    "        dp = [0]*n\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[i][0] < box[j][0] and box[i][1] < box[j][1] and box[i][2] < box[j][2]:\n",
    "                    dp[i] = max(dp[i], dp[j]+box[i][2])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        n = len(box)\n",
    "        box.sort(key=lambda o: o[0] * o[1] * o[2], reverse=True)\n",
    "        dp = [0] * n\n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if box[i][0] < box[j][0] and box[i][1] < box[j][1] and box[i][2] < box[j][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        n=len(box)\n",
    "        dp=[0]*n\n",
    "        box.sort()\n",
    "        for i in range(n):\n",
    "            dp[i]=box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[j][0]<box[i][0] and box[j][1]<box[i][1] and box[j][2]<box[i][2]:\n",
    "                    dp[i]=max(dp[i],dp[j]+box[i][2])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box.sort(reverse=True)\n",
    "\n",
    "        f = []\n",
    "        for i in range(len(box)):\n",
    "            wi, di, hi = box[i]\n",
    "            max_h = 0\n",
    "            for j in range(i):\n",
    "                wj, dj, hj = box[j]\n",
    "                if wj > wi and dj > di and hj > hi:\n",
    "                    max_h = max(max_h, f[j])\n",
    "            f += [max_h + hi]\n",
    "        \n",
    "        return max(f)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box.sort()\n",
    "        dp = [0] * len(box)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for row in range(len(box)):\n",
    "            dp[row] = box[row][2]\n",
    "            for col in range(0, row):\n",
    "                if box[col][0] < box[row][0] and box[col][1] < box[row][1] \\\n",
    "                    and box[col][2] < box[row][2]:\n",
    "                    dp[row] = max(dp[row], dp[col] + box[row][2]) \n",
    "\n",
    "            res = max(res, dp[row])\n",
    "        \n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        n=len(box)\n",
    "        box.sort()\n",
    "        dp=[0]*n\n",
    "        for i in range(n):\n",
    "            dp[i]=box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[j][0]<box[i][0] and box[j][1]<box[i][1] and box[j][2]<box[i][2]:\n",
    "                    dp[i]=max(dp[i],dp[j]+box[i][2])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        dp=[0]*len(box)\n",
    "        box.sort()\n",
    "        for i in range(len(box)):\n",
    "            dp[i]=box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[j][0]<box[i][0] and box[j][1]<box[i][1] and box[j][2]<box[i][2]:\n",
    "                    dp[i]=max(dp[i],dp[j]+box[i][2])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        dp = [0 for _ in range(len(box))]\n",
    "        box.sort()\n",
    "\n",
    "        for i in range(len(box)):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[j][0] < box[i][0] and box[j][1] < box[i][1] and box[j][2] < box[i][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box.sort()\n",
    "        # dp[i] 以box[i]结尾的最大高度和\n",
    "        # 转移:\n",
    "        # dp[i] = max(dp[j] + 1) for box[j] 满足 box[i] > box[j]\n",
    "        dp = [0] * len(box)\n",
    "        dp[0] = box[0][2]\n",
    "        # dp[i] = max(dp[i-1])\n",
    "        def boxGE(box1, box2):\n",
    "            return box1[0] > box2[0] and box1[1] > box2[1] and box1[2] > box2[2]\n",
    "        # 即找一个h和最大的递增子序列\n",
    "        #print(box)\n",
    "        ans = dp[0]\n",
    "        for i in range(1, len(box)):\n",
    "            #print(f\"cal dp[{i}] box[{i}]:{box[i]}\")\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(0, i):\n",
    "                #print(f\"dp[{j}] = {dp[j]} box:{box[j]}\")\n",
    "                if boxGE(box[i], box[j]):\n",
    "                    #print(f\"{box[i]} > {box[j]}, dp[{i}] = max({dp[i]}, {dp[j]} + {box[i][2]})\")\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "            ans = max(ans, dp[i])\n",
    "        #print(dp)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        \n",
    "        \n",
    "        # 设dp[i]表示以box[i]个箱子为底，整个堆的最大高度\n",
    "        # 这里需要注意，并不一定将所有箱子都用上，可以只有一部分，只要最高就行了\n",
    "        box.sort()\n",
    "        dp = [1] * len(box)\n",
    "        for i in range(len(box)):\n",
    "            dp[i] = box[i][2]\n",
    "\n",
    "            for j in range(i):\n",
    "                if box[j][0]<box[i][0] and box[j][1]<box[i][1] and box[j][2]<box[i][2]:\n",
    "                    dp[i] = max(dp[i],dp[j]+box[i][2])\n",
    "        return max(dp)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        dp = [0 for _ in range(len(box))]\n",
    "        box.sort()\n",
    "\n",
    "        for i in range(len(box)):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[j][0] < box[i][0] and box[j][1] < box[i][1] and box[j][2] < box[i][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        n = len(box)\n",
    "        dp = [0] * n\n",
    "        box.sort(key=lambda x : x[2])\n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            tmp = 0\n",
    "            w1,d1,h1 = box[i]\n",
    "            for j in range(i+1):\n",
    "                w2, d2, h2 = box[j]\n",
    "                if w1 > w2 and d1 > d2 and h1 > h2:\n",
    "                    tmp = max(tmp, dp[j])\n",
    "            dp[i] += tmp\n",
    "        print(dp)\n",
    "        return max(dp)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        def smaller(a, b):\n",
    "            if a[0] < b[0] and a[1] < b[1] and a[2] < b[2]:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        box.sort()\n",
    "        n = len(box)\n",
    "        dp = [x[2] for x in box]\n",
    "        for i in range(n):\n",
    "            tmp = 0\n",
    "            for j in range(i):\n",
    "                if smaller(box[j], box[i]):\n",
    "                    tmp = max(tmp, dp[j])\n",
    "            dp[i] += tmp\n",
    "        return max(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, xiangzi: List[List[int]]) -> int:\n",
    "        xiangzi.sort(key=lambda x: (x[0], x[1], x[2]))\n",
    "        # print(xiangzi)\n",
    "        n = len(xiangzi)\n",
    "        dp = [0]*n\n",
    "        for i in range(n):\n",
    "            dp[i]=xiangzi[i][-1]\n",
    "        for i in range(n):\n",
    "            temp = dp[i]\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if xiangzi[i][0]>xiangzi[j][0] and xiangzi[i][1]>xiangzi[j][1] and xiangzi[i][2]>xiangzi[j][2]:\n",
    "                    temp = max(temp,dp[i]+dp[j])\n",
    "            dp[i] = temp\n",
    "        # print(dp)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        n = len(box)\n",
    "        dp = [0] * (n + 1)\n",
    "\n",
    "        box.sort(key=lambda x: x[0])\n",
    "        dp[0] = box[0][2]\n",
    "        ans = dp[0]\n",
    "        for i in range(1, n):\n",
    "            maxh = 0\n",
    "            for j in range(i):\n",
    "                if box[i][0] > box[j][0] and \\\n",
    "                   box[i][1] > box[j][1] and \\\n",
    "                   box[i][2] > box[j][2]:\n",
    "                    maxh = max(maxh, dp[j]); # if not avaliable, maxh = 0, dp[i] should be box[i][2]\n",
    "            dp[i] = maxh + box[i][2]\n",
    "            ans = max(ans, dp[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box.sort()\n",
    "        f = []\n",
    "        for i in range(len(box)):\n",
    "            x1, y1, z1 = box[i]\n",
    "            cur = 0\n",
    "            for j in range(i):\n",
    "                x2, y2, z2 = box[j]\n",
    "                if x2 < x1 and y2 < y1 and z2 < z1:\n",
    "                    cur = max(cur, f[j])\n",
    "            f.append(cur + z1)\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        dp = [0 for _ in range(len(box))]\n",
    "        box.sort()\n",
    "        for i in range(len(box)):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[j][0] < box[i][0] and box[j][1] < box[i][1] and box[j][2] < box[i][2]:\n",
    "                    dp[i] = max(dp[i],dp[j] + box[i][2])\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        dp = [0 for _ in range(len(box))]\n",
    "        box.sort()\n",
    "\n",
    "        for i in range(len(box)):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[j][0] < box[i][0] and box[j][1] < box[i][1] and box[j][2] < box[i][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        # 记忆搜索\n",
    "        # n = len(box)\n",
    "        # @cache\n",
    "        # def dfs(w,d,h):\n",
    "        #     tmp = [(w0,d0,h0) for w0,d0,h0 in box if w0<w and d0<d and h0<h]\n",
    "        #     if not tmp:return h\n",
    "        #     return max(dfs(w0,d0,h0) for w0,d0,h0 in tmp)+h\n",
    "        # return max(dfs(w,d,h) for w,d,h in box)\n",
    "\n",
    "        # 动态规划\n",
    "        n = len(box)\n",
    "        box.sort(key=lambda x:(x[0]))\n",
    "        dp = [0]*n\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[i][0]>box[j][0] and box[i][1]>box[j][1] and box[i][2]>box[j][2]:\n",
    "                    dp[i] = max(dp[i],dp[j]+box[i][2])\n",
    "            res = max(res,dp[i])\n",
    "        return res\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        n = len(box)\n",
    "        dp = [0] * n\n",
    "        box.sort(key=lambda x:(x[0]))\n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if all(box[j][k] < box[i][k] for k in range(0,3)):\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    因为要求下层箱子的宽、深、高都必须大于上面箱子的高度，\n",
    "    因此我们可以先对箱子进行排序，排序依据为(h,w,d)\n",
    "    接下来我们采用动态规划算法进行求解：\n",
    "    定义：\n",
    "        dp[i]表示最后一个箱子为第i个箱子时，所能达到的最大高度。\n",
    "    转移方程:\n",
    "        dp[i] = max{dp[k] for k in range(i) if box[k]>box[i], 0} + box[i].h\n",
    "    初始条件:\n",
    "        dp[0] = box[0].h\n",
    "    返回值：\n",
    "        dp.max()\n",
    "    \"\"\"\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        N: int = len(box)\n",
    "        box.sort(key=lambda x: (x[2]), reverse=True)\n",
    "        dp = [0 for _ in range(N)]\n",
    "        dp[0] = box[0][2]\n",
    "        for i in range(1,N):\n",
    "            dp[i]=box[i][2]\n",
    "            for k in range(i):\n",
    "                if box[k][0]>box[i][0] and box[k][1]>box[i][1] and box[k][2]>box[i][2]:\n",
    "                    dp[i] = max(dp[i], dp[k] + box[i][2])\n",
    "        \n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        dp = [0 for _ in range(len(box))]\n",
    "        box.sort()\n",
    "\n",
    "        for i in range(len(box)):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[j][0] < box[i][0] and box[j][1] < box[i][1] and box[j][2] < box[i][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        dp = [0] * len(box)\n",
    "        box.sort()\n",
    "\n",
    "        for i in range(len(box)):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[j][0] < box[i][0] and box[j][1] < box[i][1] and box[j][2] < box[i][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        首先对box排序，规则是宽 高 深\n",
    "        然后dp[i]代表在一定使用了第i个箱子后，前i个箱子所能组成的最大高度\n",
    "        ！！！注意这里一定使用第i个箱子！！！ 因此dp[i]不一定大于dp[j]\n",
    "        那么为什么不让dp[i]代表前i个箱子的最大呢 因为比如这种情况\n",
    "        [[1,2,4],[2,1,2],[3,2,3]] dp[0]=4  dp[1]=4 dp[2]=4+3=7 但显然7这个答案是错误的 \n",
    "        错误的原因就是 排序后后面的元素不一定是大于前面的元素的\n",
    "        dp[i] = box[i][-1]+max(dp[j]) for j in range(i) 且box[i][k]>box[j][k] for k in [0,1,2] \n",
    "        为啥最后取max不是取dp[-1] 因为后面的元素不是严格大于前面的，比如\n",
    "        [[1,2,2],[2,3,4],[4,5,6],[100,1,1]]最后一个元素是[100,1,1]没法和前面的累积 只能单独成列\n",
    "        因此最后取最大\n",
    "        \"\"\"\n",
    "        box.sort(key=lambda x:(x[0],x[1],x[2]))\n",
    "        n = len(box)\n",
    "        dp = [box[i][-1] for i in range(n)] #初始是自己的高度\n",
    "        for i in range(1,n):\n",
    "            for j in range(i):\n",
    "                if all(box[i][k]>box[j][k] for k in [0,1,2]):#三个条件均需要满足\n",
    "                    dp[i] = max(dp[i],dp[j]+box[i][-1])\n",
    "        return max(dp) \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box.sort(key=lambda x: (x[0], -x[1]))\n",
    "        dp = [0 for _ in range(len(box))]\n",
    "        for i in range(len(box)):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[j][1] < box[i][1] and box[j][2] < box[i][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        首先对box排序，规则是宽 高 深\n",
    "        然后dp[i]代表在一定使用了第i个箱子后，前i个箱子所能组成的最大高度\n",
    "        ！！！注意这里一定使用第i个箱子！！！ 因此dp[i]不一定大于dp[j]\n",
    "        dp[i] = box[i][-1]+max(dp[j]) for j in range(i) 且box[i][k]>box[j][k] for k in [0,1,2] \n",
    "        为啥最后取max不是取dp[-1] 因为后面的元素不是严格大于前面的，比如\n",
    "        [[1,2,2],[2,3,4],[4,5,6],[100,1,1]]最后一个元素是[100,1,1]没法和前面的累积 只能单独成列\n",
    "        因此最后取最大\n",
    "        \"\"\"\n",
    "        box.sort(key=lambda x:(x[0],x[1],x[2]))\n",
    "        n = len(box)\n",
    "        dp = [box[i][-1] for i in range(n)] #初始是自己的高度\n",
    "        for i in range(1,n):\n",
    "            for j in range(i):\n",
    "                if all(box[i][k]>box[j][k] for k in [0,1,2]):#三个条件均需要满足\n",
    "                    dp[i] = max(dp[i],dp[j]+box[i][-1])\n",
    "        return max(dp) \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box.sort(key=lambda x: x[0])\n",
    "        n = len(box)\n",
    "        f = [0] * n\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if (\n",
    "                    box[i][0] > box[j][0]\n",
    "                    and box[i][1] > box[j][1]\n",
    "                    and box[i][2] > box[j][2]\n",
    "                ):\n",
    "                    f[i] = max(f[i], f[j])\n",
    "            f[i] += box[i][2]\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box.sort()\n",
    "        ans=[0]*len(box)\n",
    "        for i in range(len(box)):\n",
    "            ans[i]=box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[i][0]>box[j][0] and box[i][1]>box[j][1] and box[i][2]>box[j][2]:\n",
    "                    ans[i]=max(ans[i],ans[j]+box[i][2])\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box = sorted(box, key=lambda x:(x[0], x[1], x[2]))\n",
    "        dp = [0]*(len(box) + 1)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(len(box)):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[j][0] < box[i][0] and box[j][1] < box[i][1] and box[j][2] < box[i][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "            ans = max(ans, dp[i])\n",
    "        # print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        n = len(box)\n",
    "        box.sort(key=lambda x: (x[0], -x[1]))\n",
    "        dp = [0] * n\n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[j][0] < box[i][0] and box[j][1] < box[i][1] and box[j][2] < box[i][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box.sort(key=lambda x:x[0])\n",
    "        rs = []\n",
    "        height = 0\n",
    "        for i in range(len(box)):\n",
    "            rs.append(box[i][2])\n",
    "            for j in range(i):\n",
    "                if box[i][0]>box[j][0] and box[i][1]>box[j][1] and box[i][2]>box[j][2]:\n",
    "                    rs[i] = max(rs[i], rs[j]+box[i][2])\n",
    "            height = max(height, rs[i])\n",
    "        return height"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box.sort()\n",
    "        dp = [0] * len(box)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for row in range(len(box)):\n",
    "            dp[row] = box[row][2]\n",
    "            for col in range(0, row):\n",
    "                if box[col][0] < box[row][0] and box[col][1] < box[row][1] \\\n",
    "                    and box[col][2] < box[row][2]:\n",
    "                    dp[row] = max(dp[row], dp[col] + box[row][2]) \n",
    "\n",
    "            res = max(res, dp[row])\n",
    "        \n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box = sorted(box)\n",
    "        dp = [0 for _ in range(len(box))]\n",
    "        dp[0] = box[0][2]\n",
    "        for i in range(1, len(box)):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                dp[i] = max(dp[j]+box[i][2], dp[i]) if box[j][2] < box[i][2] and box[j][1] < box[i][1] and box[j][0] < box[i][0] else dp[i]\n",
    "        return(max(dp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        # 记忆搜索\n",
    "        # n = len(box)\n",
    "        # @cache\n",
    "        # def dfs(w,d,h):\n",
    "        #     tmp = [(w0,d0,h0) for w0,d0,h0 in box if w0<w and d0<d and h0<h]\n",
    "        #     if not tmp:return h\n",
    "        #     return max(dfs(w0,d0,h0) for w0,d0,h0 in tmp)+h\n",
    "        # return max(dfs(w,d,h) for w,d,h in box)\n",
    "\n",
    "        # 动态规划\n",
    "        n = len(box)\n",
    "        box.sort(key=lambda x:(x[0],x[1],x[2]))\n",
    "        dp = [0]*n\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[i][0]>box[j][0] and box[i][1]>box[j][1] and box[i][2]>box[j][2]:\n",
    "                    dp[i] = max(dp[i],dp[j]+box[i][2])\n",
    "            res = max(res,dp[i])\n",
    "        return res\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box.sort()\n",
    "        # dp[i] 以box[i]结尾的最大高度和\n",
    "        # 转移:\n",
    "        # dp[i] = max(dp[j] + 1) for box[j] 满足 box[i] > box[j]\n",
    "        dp = [0 for _ in range(len(box))]\n",
    "        dp[0] = box[0][2]\n",
    "        # dp[i] = max(dp[i-1])\n",
    "        def boxGE(box1, box2):\n",
    "            return box1[0] > box2[0] and box1[1] > box2[1] and box1[2] > box2[2]\n",
    "        # 即找一个h和最大的递增子序列\n",
    "        #print(box)\n",
    "        ans = dp[0]\n",
    "        for i in range(1, len(box)):\n",
    "            #print(f\"cal dp[{i}] box[{i}]:{box[i]}\")\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(0, i):\n",
    "                #print(f\"dp[{j}] = {dp[j]} box:{box[j]}\")\n",
    "                if boxGE(box[i], box[j]):\n",
    "                    #print(f\"{box[i]} > {box[j]}, dp[{i}] = max({dp[i]}, {dp[j]} + {box[i][2]})\")\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "            ans = max(ans, dp[i])\n",
    "        #print(dp)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box.sort()\n",
    "        dp = [0] * len(box)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for row in range(len(box)):\n",
    "            dp[row] = box[row][2]\n",
    "            for col in range(0, row):\n",
    "                if box[col][0] < box[row][0] and box[col][1] < box[row][1] \\\n",
    "                    and box[col][2] < box[row][2]:\n",
    "                    dp[row] = max(dp[row], dp[col] + box[row][2]) \n",
    "\n",
    "            res = max(res, dp[row])\n",
    "        \n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        n=len(box)\n",
    "        box.sort()\n",
    "        dp=[0]*n\n",
    "        for i in range(n):\n",
    "            dp[i]=box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[i][0]>box[j][0] and box[i][1]>box[j][1] and box[i][2]>box[j][2]:\n",
    "                    dp[i]=max(dp[i],dp[j]+box[i][2])\n",
    "        return max(dp)\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box.sort()\n",
    "        dp = [0] * len(box)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for row in range(len(box)):\n",
    "            dp[row] = box[row][2]\n",
    "            for col in range(0, row):\n",
    "                if box[col][0] < box[row][0] and box[col][1] < box[row][1] \\\n",
    "                    and box[col][2] < box[row][2]:\n",
    "                    dp[row] = max(dp[row], dp[col] + box[row][2]) \n",
    "\n",
    "            res = max(res, dp[row])\n",
    "        \n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        n = len(box) \n",
    "        box.sort(key=lambda x:x[0]*1000000+x[1]*1000+x[2])\n",
    "        dp =  [ b [2] for b in box]\n",
    "        for i in range(1,n):\n",
    "            for j in range(i):\n",
    "                if box[j][0]<box[i][0] and box[j][1]<box[i][1] and box[j][2]<box[i][2]:\n",
    "                    dp[i] = max(dp[i],dp[j] + box[i][2])\n",
    "        return max(dp )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        \n",
    "        dp = [0 for _ in range(len(box))]\n",
    "        \n",
    "        box.sort()\n",
    "\n",
    "        for i in range(len(box)):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[j][0] < box[i][0] and box[j][1] < box[i][1] and box[j][2] < box[i][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "# python3 动态规划\n",
    "# 最长上升子序列，最简单的方式就是 o(n**2) 的动规。 dp[i] 代表以第 i 个箱子放在最底下的最大高度。\n",
    "# 作者：yesOhh\n",
    "# 链接：https://leetcode.cn/problems/pile-box-lcci/solutions/102261/python3-dong-tai-gui-hua-by-yesohh/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        # 记忆搜索\n",
    "        # n = len(box)\n",
    "        # @cache\n",
    "        # def dfs(w,d,h):\n",
    "        #     tmp = [(w0,d0,h0) for w0,d0,h0 in box if w0<w and d0<d and h0<h]\n",
    "        #     if not tmp:return h\n",
    "        #     return max(dfs(w0,d0,h0) for w0,d0,h0 in tmp)+h\n",
    "        # return max(dfs(w,d,h) for w,d,h in box)\n",
    "\n",
    "        # 动态规划\n",
    "        n = len(box)\n",
    "        box.sort(key=lambda x:(x[0],-x[1]))\n",
    "        dp = [0]*n\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[i][0]>box[j][0] and box[i][1]>box[j][1] and box[i][2]>box[j][2]:\n",
    "                    dp[i] = max(dp[i],dp[j]+box[i][2])\n",
    "            res = max(res,dp[i])\n",
    "        return res\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #10:47\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        if not box:\n",
    "            return 0\n",
    "        box.sort()\n",
    "        dp=[0 for _ in range(len(box))]\n",
    "        box.sort()\n",
    "\n",
    "        for i in range(len(box)):\n",
    "            dp[i]=box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[j][0]<box[i][0] and box[j][1]<box[i][1] and box[j][2]<box[i][2]:\n",
    "                    dp[i]=max(dp[i],dp[j]+box[i][2])\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        dp = [0 for _ in range(len(box))]\n",
    "        box.sort()\n",
    "\n",
    "        for i in range(len(box)):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[j][0] < box[i][0] and box[j][1] < box[i][1] and box[j][2] < box[i][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "         \n",
    "        box=sorted(box)\n",
    "        dp=[0 for _ in range(len(box))]\n",
    "        dp[0]=box[0][2]\n",
    "        for i in range(1,len(box)):\n",
    "            x=[dp[k]+box[i][2] for k in range(i) if box[k][0]<box[i][0] and box[k][1]<box[i][1] and box[k][2]<box[i][2]]\n",
    "            dp[i]=max(x) if len(x) else box[i][2]\n",
    "            \n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        n = len(box)\n",
    "        dp = [0] * n\n",
    "        box.sort(key=lambda x:(x[0],-x[1]))\n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if all(box[j][k] < box[i][k] for k in range(1,3)):\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box = sorted(box, key = lambda x: (-x[0], -x[1], -x[2]))\n",
    "        height = [0] * len(box)\n",
    "\n",
    "        def isLarger(i, j):\n",
    "            return box[i][0] > box[j][0] and box[i][1] > box[j][1] and box[i][2] > box[j][2]\n",
    "\n",
    "        for i in range(len(box)):\n",
    "            height[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if isLarger(j, i):\n",
    "                    height[i] = max(height[i], height[j] + box[i][2])\n",
    "        return max(height)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        n = len(box)\n",
    "        box.sort(key = lambda x: (x[0], -x[1]))\n",
    "        dp = [0] * n\n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if all(box[j][k] < box[i][k] for k in range(1, 3)):\n",
    "                    dp[i] = max(dp[i], dp[j]+box[i][2])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box2 = sorted(box, key=lambda x:(x[0],x[1],x[2]))\n",
    "        print(box2)\n",
    "        n = len(box)\n",
    "        dp = [0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if box2[j][0] < box2[i][0] and box2[j][1] < box2[i][1] and box2[j][2] < box2[i][2] and dp[j] > dp[i]:\n",
    "                    dp[i] = dp[j]\n",
    "            dp[i] += box2[i][2]\n",
    "        print(dp)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box = tuple(sorted(box))\n",
    "        dp = [h for _, _, h in box]\n",
    "        for i in range(len(box)):\n",
    "            for j in range(i):\n",
    "                if all(s > t for s, t in zip(box[i], box[j])):\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        n = len(box)\n",
    "        dp = [0] * n\n",
    "        box.sort(key=lambda x:(x[0],-x[1]))\n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if all(box[j][k] < box[i][k] for k in range(1,3)):\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        # wi上升序，相同的wi，di按照降序排列\n",
    "        box.sort(key=lambda x: (x[0], -x[1]))\n",
    "        dp = [0 for _ in range(len(box))]\n",
    "        for i in range(len(box)):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                # wi上已经排序了，无需再比较box[i][0]\n",
    "                if box[j][1] < box[i][1] and box[j][2] < box[i][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        # 记忆搜索\n",
    "        # n = len(box)\n",
    "        # @cache\n",
    "        # def dfs(w,d,h):\n",
    "        #     tmp = [(w0,d0,h0) for w0,d0,h0 in box if w0<w and d0<d and h0<h]\n",
    "        #     if not tmp:return h\n",
    "        #     return max(dfs(w0,d0,h0) for w0,d0,h0 in tmp)+h\n",
    "        # return max(dfs(w,d,h) for w,d,h in box)\n",
    "\n",
    "        # 动态规划\n",
    "        n = len(box)\n",
    "        box.sort(key=lambda x:(x[0],x[1],x[2]))\n",
    "        dp = [0]*n\n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[i][0]>box[j][0] and box[i][1]>box[j][1] and box[i][2]>box[j][2]:\n",
    "                    dp[i] = max(dp[i],dp[j]+box[i][2])\n",
    "        return max(dp)\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        # 记忆搜索\n",
    "        # n = len(box)\n",
    "        # @cache\n",
    "        # def dfs(w,d,h):\n",
    "        #     tmp = [(w0,d0,h0) for w0,d0,h0 in box if w0<w and d0<d and h0<h]\n",
    "        #     if not tmp:return h\n",
    "        #     return max(dfs(w0,d0,h0) for w0,d0,h0 in tmp)+h\n",
    "        # return max(dfs(w,d,h) for w,d,h in box)\n",
    "\n",
    "        # 动态规划\n",
    "        n = len(box)\n",
    "        box.sort(key=lambda x:(x[0],x[1],x[2]))\n",
    "        dp = [0]*n\n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[i][0]>box[j][0] and box[i][1]>box[j][1] and box[i][2]>box[j][2]:\n",
    "                    dp[i] = max(dp[i],dp[j]+box[i][2])\n",
    "        return max(dp)\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        n = len(box)\n",
    "        dp = [0] * n\n",
    "        box.sort(key=lambda x:(x[0],-x[1]))\n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if all(box[j][k] < box[i][k] for k in range(1,3)):\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box.sort()\n",
    "        n = len(box)\n",
    "        dp = [0]*(n+2)\n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in reversed(range(i)):\n",
    "                if box[i][0] > box[j][0] and box[i][1] > box[j][1] and box[i][2] > box[j][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp[:n])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        dp = [0 for _ in range(len(box))]\n",
    "        box.sort()\n",
    "\n",
    "        for i in range(len(box)):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[j][0] < box[i][0] and box[j][1] < box[i][1] and box[j][2] < box[i][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        # 记忆搜索\n",
    "        # n = len(box)\n",
    "        # @cache\n",
    "        # def dfs(w,d,h):\n",
    "        #     tmp = [(w0,d0,h0) for w0,d0,h0 in box if w0<w and d0<d and h0<h]\n",
    "        #     if not tmp:return h\n",
    "        #     return max(dfs(w0,d0,h0) for w0,d0,h0 in tmp)+h\n",
    "        # return max(dfs(w,d,h) for w,d,h in box)\n",
    "\n",
    "        # 动态规划\n",
    "        n = len(box)\n",
    "        box.sort(key=lambda x:(x[0],x[1],x[2]))\n",
    "        dp = [0]*n\n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[i][0]>box[j][0] and box[i][1]>box[j][1] and box[i][2]>box[j][2]:\n",
    "                    dp[i] = max(dp[i],dp[j]+box[i][2])\n",
    "        return max(dp)\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        # 记忆搜索\n",
    "        n = len(box)\n",
    "        @cache\n",
    "        def dfs(w,d,h):\n",
    "            tmp = [(w0,d0,h0) for w0,d0,h0 in box if w0<w and d0<d and h0<h]\n",
    "            if not tmp:return h\n",
    "            return max(dfs(w0,d0,h0) for w0,d0,h0 in tmp)+h\n",
    "        return max(dfs(w,d,h) for w,d,h in box)\n",
    "\n",
    "        # 动态规划\n",
    "        # n = len(box)\n",
    "        # box.sort(key=lambda x:(x[0]))\n",
    "        # dp = [0]*n\n",
    "        # res = 0\n",
    "        # for i in range(n):\n",
    "        #     dp[i] = box[i][2]\n",
    "        #     for j in range(i):\n",
    "        #         if box[i][0]>box[j][0] and box[i][1]>box[j][1] and box[i][2]>box[j][2]:\n",
    "        #             dp[i] = max(dp[i],dp[j]+box[i][2])\n",
    "        #     res = max(res,dp[i])\n",
    "        # return res\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box = sorted(box, key=lambda x: (x[0], -x[1]))\n",
    "        n = len(box)\n",
    "\n",
    "        dp = [0] * n \n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[j][0] < box[i][0] and box[j][1] < box[i][1] and box[j][2] < box[i][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    因为要求下层箱子的宽、深、高都必须大于上面箱子的高度，\n",
    "    因此我们可以先对箱子进行排序，排序依据为(h,w,d)\n",
    "    接下来我们采用动态规划算法进行求解：\n",
    "    定义：\n",
    "        dp[i]表示最后一个箱子为第i个箱子时，所能达到的最大高度。\n",
    "    转移方程:\n",
    "        dp[i] = max{dp[k] for k in range(i) if box[k]>box[i], 0} + box[i].h\n",
    "    初始条件:\n",
    "        dp[0] = box[0].h\n",
    "    返回值：\n",
    "        dp.max()\n",
    "    \"\"\"\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        N: int = len(box)\n",
    "        box.sort(key=lambda x: (x[2],x[0],x[1]), reverse=True)\n",
    "        dp = [0 for _ in range(N)]\n",
    "        dp[0] = box[0][2]\n",
    "        for i in range(1,N):\n",
    "            dp[i]=box[i][2]\n",
    "            for k in range(i):\n",
    "                if box[k][0]>box[i][0] and box[k][1]>box[i][1] and box[k][2]>box[i][2]:\n",
    "                    dp[i] = max(dp[i], dp[k] + box[i][2])\n",
    "        \n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        # 记忆搜索\n",
    "        # n = len(box)\n",
    "        # @cache\n",
    "        # def dfs(w,d,h):\n",
    "        #     tmp = [(w0,d0,h0) for w0,d0,h0 in box if w0<w and d0<d and h0<h]\n",
    "        #     if not tmp:return h\n",
    "        #     return max(dfs(w0,d0,h0) for w0,d0,h0 in tmp)+h\n",
    "        # return max(dfs(w,d,h) for w,d,h in box)\n",
    "\n",
    "        # 动态规划\n",
    "        n = len(box)\n",
    "        box.sort(key=lambda x:(x[0],-x[1]))\n",
    "        dp = [0]*n\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[i][0]>box[j][0] and box[i][1]>box[j][1] and box[i][2]>box[j][2]:\n",
    "                    dp[i] = max(dp[i],dp[j]+box[i][2])\n",
    "            res = max(res,dp[i])\n",
    "        return res\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        n = len(box)\n",
    "        dp = [0] * n\n",
    "        box.sort(key=lambda x:(x[0], x[1]))\n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if all(box[j][k] < box[i][k] for k in range(0,3)):\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]):\n",
    "        # wi上升序，相同的wi，di按照降序排列\n",
    "        box.sort(key=lambda x: (x[0], -x[1]))\n",
    "        dp = [0 for _ in range(len(box))]\n",
    "        for i in range(len(box)):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                # wi上已经排序了，无需再比较box[i][0]\n",
    "                if box[j][1] < box[i][1] and box[j][2] < box[i][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        n = len(box)\n",
    "        \n",
    "        box.sort(key = lambda k: (k[0], -k[1]))\n",
    "        dp = [b[2] for b in box]\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if box[i][2] > box[j][2] and box[i][1] > box[j][1] and box[i][0] > box[j][0]:\n",
    "                    dp[i] = max(dp[j] + box[i][2], dp[i])\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box = sorted(box, key=lambda x: (x[0], x[1]))\n",
    "        n = len(box)\n",
    "\n",
    "        dp = [0] * n \n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if box[j][0] < box[i][0] and box[j][1] < box[i][1] and box[j][2] < box[i][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box.sort(key = lambda x: (-x[0], x[1], x[2]))\n",
    "        n = len(box)\n",
    "        dp = [b[2] for b in box]\n",
    "        print(box)\n",
    "        maxHeight = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if box[i][1] < box[j][1] and box[i][2] < box[j][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "            maxHeight = max(maxHeight, dp[i])\n",
    "        print(dp)\n",
    "        return maxHeight"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        n = len(box)\n",
    "        dp = [0] * n\n",
    "        box.sort(key=lambda x:(x[0],-x[1]))\n",
    "        for i in range(n):\n",
    "            dp[i] = box[i][2]\n",
    "            for j in range(i):\n",
    "                if all(box[j][k] < box[i][k] for k in range(1,3)):\n",
    "                    dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        return max(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        # 记忆搜索\n",
    "        n = len(box)\n",
    "        @cache\n",
    "        def dfs(w,d,h):\n",
    "            tmp = [(w0,d0,h0) for w0,d0,h0 in box if w0<w and d0<d and h0<h]\n",
    "            if not tmp:return h\n",
    "            return max(dfs(w0,d0,h0) for w0,d0,h0 in tmp)+h\n",
    "        return max(dfs(w,d,h) for w,d,h in box)\n",
    "\n",
    "        # 动态规划\n",
    "        # n = len(box)\n",
    "        # box.sort(key=lambda x:(x[0]))\n",
    "        # dp = [0]*n\n",
    "        # res = 0\n",
    "        # for i in range(n):\n",
    "        #     dp[i] = box[i][2]\n",
    "        #     for j in range(i):\n",
    "        #         if box[i][0]>box[j][0] and box[i][1]>box[j][1] and box[i][2]>box[j][2]:\n",
    "        #             dp[i] = max(dp[i],dp[j]+box[i][2])\n",
    "        #     res = max(res,dp[i])\n",
    "        # return res\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        n = len(box)\n",
    "        @cache\n",
    "        def dfs(w,d,h):\n",
    "            tmp = [(w0,d0,h0) for w0,d0,h0 in box if w0<w and d0<d and h0<h]\n",
    "            if not tmp:return h\n",
    "            return max(dfs(w0,d0,h0) for w0,d0,h0 in tmp)+h\n",
    "        return max(dfs(w,d,h) for w,d,h in box)\n",
    "\n",
    "        # n = len(box)\n",
    "        # box.sort(key=lambda x:(x[0],x[1],x[2]))\n",
    "        # dp = [0]*n\n",
    "        # w0,d0,h0 = 0,0,0\n",
    "        # for i in range(n):\n",
    "        #     dp[i] = max(dp[:i])\n",
    "        #     if box[i-1][0]>w0 and box[i-1][1]>d0 and box[i-1][2]>h0:\n",
    "        #         dp[i] += box[i-1][2]\n",
    "        # return dp[-1]\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        # n^2超时\n",
    "        # n = len(box)\n",
    "        # dp = [0] * n\n",
    "        # box.sort(key=lambda x:(x[0],-x[1]))\n",
    "        # for i in range(n):\n",
    "        #     dp[i] = box[i][2]\n",
    "        #     for j in range(i):\n",
    "        #         if all(box[j][k] < box[i][k] for k in range(1, 3)):\n",
    "        #             dp[i] = max(dp[i], dp[j] + box[i][2])\n",
    "        # return max(dp)\n",
    "\n",
    "        @cache\n",
    "        def dfs(w, d, h):\n",
    "            inners = [(iw, id, ih) for iw, id, ih in box if iw < w and id < d and ih < h]\n",
    "            if not inners: return h\n",
    "            return max(dfs(iw, id, ih) for iw, id, ih in inners) + h\n",
    "        return max(dfs(w, d, h) for w, d, h in box)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        # 记忆搜索\n",
    "        n = len(box)\n",
    "        @cache\n",
    "        def dfs(w,d,h):\n",
    "            tmp = [(w0,d0,h0) for w0,d0,h0 in box if w0<w and d0<d and h0<h]\n",
    "            if not tmp:return h\n",
    "            return max(dfs(w0,d0,h0) for w0,d0,h0 in tmp)+h\n",
    "        return max(dfs(w,d,h) for w,d,h in box)\n",
    "\n",
    "        # 动态规划\n",
    "        # n = len(box)\n",
    "        # box.sort(key=lambda x:(x[0]))\n",
    "        # dp = [0]*n\n",
    "        # res = 0\n",
    "        # for i in range(n):\n",
    "        #     dp[i] = box[i][2]\n",
    "        #     for j in range(i):\n",
    "        #         if box[i][0]>box[j][0] and box[i][1]>box[j][1] and box[i][2]>box[j][2]:\n",
    "        #             dp[i] = max(dp[i],dp[j]+box[i][2])\n",
    "        #     res = max(res,dp[i])\n",
    "        # return res\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        @functools.lru_cache(3000)\n",
    "        def dfs(w, d, h):\n",
    "            valid = [(wi, di, hi) for wi, di, hi in box if wi < w and di < d and hi < h]\n",
    "            if not valid:\n",
    "                return h\n",
    "            return max(dfs(wi, di, hi) for wi, di, hi in valid) + h\n",
    "        return max(dfs(w, d, h) for w, d, h in box)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        box.sort(key=lambda x: -x[-1])\n",
    "        n = len(box)\n",
    "        res = 0\n",
    "        \n",
    "        @cache\n",
    "        def dfs(w, d, h, idx):\n",
    "            if idx == n:\n",
    "                return h\n",
    "            res = 0\n",
    "            for i in range(idx, n):\n",
    "                if box[i][0] < w and box[i][1] < d and box[i][2] < h:\n",
    "                    res = max(res, dfs(box[i][0], box[i][1], box[i][2], i+1))\n",
    "            return res+h\n",
    "\n",
    "        for i in range(n):\n",
    "            res = max(res, dfs(box[i][0], box[i][1], box[i][2], i+1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pileBox(self, box: List[List[int]]) -> int:\n",
    "        @functools.lru_cache(3000)\n",
    "        def dfs(w, d, h):\n",
    "            valid = [(wi, di, hi) for wi, di, hi in box if wi < w and di < d and hi < h]\n",
    "            if not valid:\n",
    "                return h\n",
    "            return max(dfs(wi, di, hi) for wi, di, hi in valid) + h\n",
    "        return max(dfs(w, d, h) for w, d, h in box)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
